1. Field of the Invention
The present invention relates generally to memory management within a computer system, and more particularly to concurrent garbage collection.
2. Description of the Related Art
Memory management plays a crucial role in the efficient utilization of memory in a computer system. Memory that is no longer needed is termed “garbage memory” and is reclaimed by a manual process or by an automatic memory management mechanism called “garbage collection”. Memory management may be implemented as a manual process, where a developer or programmer has direct control over when and which part of memory can be recycled, or as an automatic process, where a service within the system, embedded as part of a language or as an extension, identifies and recovers expended memory. Automatic memory management frees a developer from mundane details such as coding for recovery of memory, allowing the developer to focus on developing application logic. The hardest part in memory management is to figure out when an object is no longer needed. Automatic garbage collection which has become an inherent part of memory management in most modern object-based systems resolves this issue by providing logic to identify objects no longer needed in memory.
A garbage collection running on a computer system interacts with a mutator on the system wherein an application program is executing. The mutator is capable of creating memory objects, writing values into these objects and reading values from these objects in response to the executing program. During the interaction with the mutator, the garbage collector (GC) identifies the objects that are being currently used by the mutator or needed at a later time during the execution of the application by the mutator. The GC uses various techniques, such as reference counting, for example, to dynamically compute, at regular intervals, a set of reachable objects. Reachable objects are those objects that are needed by the mutator during the execution of the application. From these reachable objects, the GC establishes a reachability graph using different algorithms, such as a mark-sweep algorithm, etc. Any object that is not identified as reachable is recycled. The fastest and easiest solution for identifying reachable and unreachable objects is by allowing the GC to stop all the mutators. The GC then finds a set of root objects. Root objects are objects that are directly referenced by the mutators or are in a location accessible by all mutators. The GC then looks through the root objects for objects that are referenced by the root objects to build a reachability graph. The drawback of stopping the mutators to build a reachability graph is that it takes up significant processing time and results in performance degradation of the system.
In order to overcome the performance degradation problem due to stopping of the mutators, concurrent garbage collection algorithm was introduced. The concurrent execution of the GC with the mutator resulted in a reachability graph that was not accurate as the set of reachable objects constantly evolved during the course of the mutator execution as described in the example illustrated in FIGS. 1A through 1E.
FIGS. 1A through 1E illustrate a high level overview of a reachability graph and marking operations associated with this reachability graph during a concurrent garbage collection cycle and a potential problem associated with this type of marking. A program executing on a mutator within a computer system references objects that are needed during the program's execution. These objects are allocated memory by a memory manager within the computer system so that the program can access these objects efficiently. A GC within the computer system regularly scans these objects and interacts with the mutator to identify objects that are in use. An object is in use if it can be accessed directly or reached by the mutator. The executing program can run in a plurality of threads with each thread actively executing a method. Each of these methods may reference one or more objects as variables. These referenced objects are part of what is called “root objects” as they are directly referenced and are immediately available to the program threads. Objects that are referenced by these root objects are “reachable” objects and objects referenced by these reachable objects are also reachable. These root and reachable objects are non-recyclable as they are being currently referenced or will be referenced by the executing program threads. Upon identifying objects that are in use, the GC can recycle the non-reachable objects as they are no longer needed by the mutator threads, and perform other operations to improve the performance of the mutator. The GC creates a “reachability” graph using the root objects and reachable objects. The objects within the reachability graph are marked such that they are not recycled. The GC might have to do recursive scan of all the objects to appropriately mark the reachable objects and build an accurate reachability graph, especially in the case where the GC is running concurrently with the mutator, as the root and reachable objects are constantly evolving.
A GC interacts with all the mutator threads to obtain a set of objects that are directly referenced by the mutator threads. In one example shown in FIG. 1A, a reachability graph is created using a root object (root node) n1 which is directly referenced by a mutator thread. Reachable objects that are referenced by the root node n1 are shown as nodes n2 and n3 and objects reachable by the reachable nodes n2 and n3 are shown as nodes n4, n5 and n6, respectively. Node n7 is reachable through node n6 and node n8 is reachable through node n7.
FIG. 1A also shows the root object n1 as being marked during the primary scan of the GC during a current cycle of garbage collection. A tri-color marking technique is utilized in this example and throughout this application. According to this marking technique, a white colored object is an unreachable object and is garbage; a gray colored object is a reachable object whose children must be examined and is not garbage; and a black colored object is a reachable object whose children have been examined and is not garbage. Other techniques to mark the objects can be used so long as the functionalities of the markings are not compromised. In the primary scan by a GC in a garbage collection cycle (GC cycle), node n1 is reachable and is marked gray, as illustrated in FIG. 1A. In the next scan by the GC, node n2 and n3 which are children nodes to root node (parent node) n1 and reachable through node n1 are grayed and the parent node n1 is blackened, as the children nodes of node n1 have already been examined, as shown in FIG. 1B. In FIG. 1C a mutator exchange occurs between nodes. Mutator exchange can occur during the execution of one or more mutator threads when a node reference of a particular node evolves and the mutator thread references a different node. According to the example illustrated in FIG. 1C, node n4 is directly reachable through root node n1 and n3 is reachable through node n2. The reachability graph is modified to reflect this change during the next step of GC cycle as shown in FIG. 1C. Nodes n7 and n8 are still reachable through n4 and are retained under node n4 as is node n6 under node n3. In the next step, nodes n5 and n6 are examined by the GC as children nodes of nodes n2 and n3, respectively, and are grayed as they are reachable through nodes n2 and n3. Nodes n2 and n3 are blackened as the children nodes n5 and n6 have been examined, as shown in FIG. 1D. The GC must notice the objects involved in the mutator exchange and examine the contents of the modified references and mark them accordingly. However, the GC does not recognize the change from the mutator exchange and, as a result, node n4 is not examined as node n1 is already blackened suggesting its children have already been examined. Consequently, the GC will skip examining node n4 during subsequent steps of the GC cycle causing node n4 to stay white and hence be recycled along with its children nodes n7 and n8. In the following step, nodes n5 and n6 are examined and blackened by the GC as there are no children nodes associated with these nodes, as shown in FIG. 1E.
In the end, even though node n4 was identified as a required object by the mutator, the marking of the nodes during the GC cycle prevented n4 and its children nodes from being identified as required objects and are recycled. To avoid such critical errors, a set of read and write barriers can be used to provide a way of identifying the modified objects so that the GC can recognize these changes and identify the modified objects, examine and mark these evolved objects prior to ending a marking phase of the GC cycle. For an efficient implementation of the GC cycle, these read/write barriers incorporated complicated logic to process the evolved objects. The complicated logic in read/write barriers have their own drawbacks. With multi-threaded applications currently implemented in most computer systems, the cost of the read/write barriers can get expensive and may lead to increase in time to execute time critical application codes making it harder to meet smaller deadlines.
In view of the foregoing, there is a need for a system and method that will overcome the aforementioned problems by implementing a garbage collection mechanism that is efficient and concurrent and is capable of meeting smaller deadlines. There is also a need for a garbage collection mechanism that is more deterministic and less intrusive.